<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>链表环检测算法解析</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            color: #333;
            line-height: 1.6;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #6e8efb 0%, #a777e3 100%);
        }
        .code-block {
            background-color: #2d3748;
            border-radius: 0.5rem;
            position: relative;
        }
        .code-header {
            background-color: #1a202c;
            border-top-left-radius: 0.5rem;
            border-top-right-radius: 0.5rem;
            padding: 0.5rem 1rem;
            display: flex;
            align-items: center;
        }
        .code-lang {
            color: #f7fafc;
            font-weight: 500;
        }
        .algorithm-card:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .highlight {
            position: relative;
            z-index: 1;
        }
        .highlight::before {
            content: '';
            position: absolute;
            z-index: -1;
            top: 0;
            bottom: 0;
            left: -0.25em;
            right: -0.25em;
            background-color: rgba(167, 119, 227, 0.3);
            transform: rotate(-1deg);
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-4 sm:px-6 lg:px-8">
        <div class="max-w-4xl mx-auto text-center">
            <h1 class="text-4xl md:text-5xl font-bold mb-6 font-serif">链表环检测算法解析</h1>
            <p class="text-xl md:text-2xl mb-8 opacity-90">探索高效判断链表中环存在的多种方法</p>
            <div class="flex justify-center space-x-4">
                <a href="#fast-slow" class="px-6 py-3 bg-white text-purple-700 font-medium rounded-full hover:bg-gray-100 transition duration-300">
                    <i class="fas fa-running mr-2"></i>快慢指针
                </a>
                <a href="#hash-table" class="px-6 py-3 bg-white bg-opacity-20 font-medium rounded-full hover:bg-opacity-30 transition duration-300">
                    <i class="fas fa-table mr-2"></i>哈希表法
                </a>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-4xl mx-auto py-12 px-4 sm:px-6 lg:px-8">
        <!-- Introduction -->
        <section class="mb-16">
            <div class="prose max-w-none">
                <p class="text-lg text-gray-700">在计算机科学中，<span class="highlight">判断链表是否存在环</span>是一个经典问题。链表中的环可能导致程序陷入无限循环或其他意外行为，因此准确检测环的存在至关重要。</p>
                <p class="text-lg text-gray-700">本文将详细介绍三种主要检测方法：<span class="font-medium text-purple-700">快慢指针算法</span>、<span class="font-medium text-purple-700">哈希表方法</span>和<span class="font-medium text-purple-700">修改节点值方法</span>，分析它们的原理、实现和优缺点。</p>
            </div>
        </section>

        <!-- Visualization -->
        <section class="mb-20 bg-white rounded-xl shadow-lg overflow-hidden">
            <div class="p-6">
                <h2 class="text-2xl font-bold mb-6 text-gray-800 font-serif">算法可视化</h2>
                <div class="mermaid">
                    graph LR
                    A[开始] --> B{有环?}
                    B -->|是| C[使用快慢指针]
                    B -->|否| D[线性遍历]
                    C --> E[指针相遇]
                    E --> F[返回true]
                    D --> G[到达终点]
                    G --> H[返回false]
                </div>
            </div>
        </section>

        <!-- Fast-Slow Pointer Algorithm -->
        <section id="fast-slow" class="mb-20">
            <div class="flex items-center mb-8">
                <div class="bg-purple-100 p-3 rounded-full mr-4">
                    <i class="fas fa-running text-purple-700 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-900 font-serif">1. 快慢指针算法</h2>
            </div>

            <div class="grid md:grid-cols-2 gap-8">
                <!-- Algorithm Explanation -->
                <div class="bg-white rounded-xl shadow-md p-6 algorithm-card transition duration-300">
                    <h3 class="text-xl font-semibold mb-4 text-purple-700">算法思路</h3>
                    <ol class="space-y-4 list-decimal pl-5">
                        <li><span class="font-medium">定义两个指针</span>：一个快指针 <code class="bg-gray-100 px-2 py-1 rounded">fast</code> 和一个慢指针 <code class="bg-gray-100 px-2 py-1 rounded">slow</code>。初始时，两个指针都指向链表的头节点。</li>
                        <li><span class="font-medium">移动指针</span>：
                            <ul class="list-disc pl-5 mt-2">
                                <li>慢指针每次移动一个节点</li>
                                <li>快指针每次移动两个节点</li>
                            </ul>
                        </li>
                        <li><span class="font-medium">检测环</span>：如果链表中存在环，则快指针最终会追上慢指针；如果没有环，快指针会到达链表尾部。</li>
                    </ol>

                    <div class="mt-6 bg-yellow-50 border-l-4 border-yellow-400 p-4">
                        <div class="flex">
                            <div class="flex-shrink-0">
                                <i class="fas fa-lightbulb text-yellow-500"></i>
                            </div>
                            <div class="ml-3">
                                <p class="text-sm text-yellow-700">
                                    <span class="font-medium">为什么有效？</span> 快指针以两倍速度移动，如果有环，它们最终会在环内相遇，就像在跑道上快跑者会追上慢跑者一样。
                                </p>
                            </div>
                        </div>
                    </div>
                </div>

                <!-- Code Example -->
                <div class="code-block">
                    <div class="code-header">
                        <span class="code-lang">Java</span>
                        <div class="ml-auto flex space-x-2">
                            <div class="w-3 h-3 rounded-full bg-red-500"></div>
                            <div class="w-3 h-3 rounded-full bg-yellow-500"></div>
                            <div class="w-3 h-3 rounded-full bg-green-500"></div>
                        </div>
                    </div>
                    <pre class="p-4 overflow-x-auto text-gray-200"><code>public class LinkedListCycleDetectorDemo {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true; // 存在环
            }
        }
        return false; // 不存在环
    }

    public static void main(String[] args) {
        // 创建带环链表
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next; // 创建环

        boolean result = hasCycle(head);
        System.out.println(result ? "链表中存在环" : "链表中不存在环");
    }
}</code></pre>
                </div>
            </div>

            <div class="mt-8 bg-white rounded-xl shadow-md p-6">
                <h3 class="text-xl font-semibold mb-4 text-purple-700">算法分析</h3>
                <div class="grid md:grid-cols-2 gap-4">
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <h4 class="font-medium text-gray-900 mb-2 flex items-center">
                            <i class="fas fa-check-circle text-green-500 mr-2"></i>优点
                        </h4>
                        <ul class="list-disc pl-5 text-gray-700">
                            <li>空间复杂度为 O(1)，不需要额外存储空间</li>
                            <li>时间复杂度为 O(n)，线性时间</li>
                            <li>实现简单优雅</li>
                        </ul>
                    </div>
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <h4 class="font-medium text-gray-900 mb-2 flex items-center">
                            <i class="fas fa-exclamation-triangle text-yellow-500 mr-2"></i>局限性
                        </h4>
                        <ul class="list-disc pl-5 text-gray-700">
                            <li>无法确定环的起始节点（需要额外步骤）</li>
                            <li>在某些特殊链表结构下可能表现不佳</li>
                        </ul>
                    </div>
                </div>
            </div>
        </section>

        <!-- Hash Table Method -->
        <section id="hash-table" class="mb-20">
            <div class="flex items-center mb-8">
                <div class="bg-blue-100 p-3 rounded-full mr-4">
                    <i class="fas fa-table text-blue-700 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-900 font-serif">2. 哈希表方法</h2>
            </div>

            <div class="grid md:grid-cols-2 gap-8">
                <!-- Algorithm Explanation -->
                <div class="bg-white rounded-xl shadow-md p-6 algorithm-card transition duration-300">
                    <h3 class="text-xl font-semibold mb-4 text-blue-700">算法思路</h3>
                    <ol class="space-y-4 list-decimal pl-5">
                        <li><span class="font-medium">使用哈希表</span>：遍历链表，将每个节点的引用存储在哈希表中</li>
                        <li><span class="font-medium">检测重复</span>：
                            <ul class="list-disc pl-5 mt-2">
                                <li>如果当前节点已存在于哈希表中，说明链表存在环</li>
                                <li>如果遍历结束无重复，则链表无环</li>
                            </ul>
                        </li>
                    </ol>

                    <div class="mt-6 bg-blue-50 border-l-4 border-blue-400 p-4">
                        <div class="flex">
                            <div class="flex-shrink-0">
                                <i class="fas fa-info-circle text-blue-500"></i>
                            </div>
                            <div class="ml-3">
                                <p class="text-sm text-blue-700">
                                    <span class="font-medium">关键点：</span> 哈希表存储的是节点引用（内存地址），而不是节点值，因为不同节点可能有相同值但实际是不同的节点。
                                </p>
                            </div>
                        </div>
                    </div>
                </div>

                <!-- Code Example -->
                <div class="code-block">
                    <div class="code-header">
                        <span class="code-lang">Java</span>
                        <div class="ml-auto flex space-x-2">
                            <div class="w-3 h-3 rounded-full bg-red-500"></div>
                            <div class="w-3 h-3 rounded-full bg-yellow-500"></div>
                            <div class="w-3 h-3 rounded-full bg-green-500"></div>
                        </div>
                    </div>
                    <pre class="p-4 overflow-x-auto text-gray-200"><code>import java.util.HashSet;

public class LinkedListCycleDetectorWithHashSetDemo {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    public static boolean hasCycle(ListNode head) {
        HashSet&lt;ListNode&gt; visited = new HashSet&lt;&gt;();

        while (head != null) {
            if (visited.contains(head)) {
                return true; // 存在环
            }
            visited.add(head);
            head = head.next;
        }
        return false; // 不存在环
    }

    public static void main(String[] args) {
        // 创建带环链表
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next; // 创建环

        boolean result = hasCycle(head);
        System.out.println(result ? "链表中存在环" : "链表中不存在环");
    }
}</code></pre>
                </div>
            </div>

            <div class="mt-8 bg-white rounded-xl shadow-md p-6">
                <h3 class="text-xl font-semibold mb-4 text-blue-700">算法分析</h3>
                <div class="grid md:grid-cols-2 gap-4">
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <h4 class="font-medium text-gray-900 mb-2 flex items-center">
                            <i class="fas fa-check-circle text-green-500 mr-2"></i>优点
                        </h4>
                        <ul class="list-disc pl-5 text-gray-700">
                            <li>实现简单直观</li>
                            <li>可以轻松扩展到查找环的起始节点</li>
                            <li>时间复杂度为 O(n)，线性时间</li>
                        </ul>
                    </div>
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <h4 class="font-medium text-gray-900 mb-2 flex items-center">
                            <i class="fas fa-exclamation-triangle text-yellow-500 mr-2"></i>局限性
                        </h4>
                        <ul class="list-disc pl-5 text-gray-700">
                            <li>空间复杂度为 O(n)，需要额外存储空间</li>
                            <li>哈希表操作有一定开销</li>
                        </ul>
                    </div>
                </div>
            </div>
        </section>

        <!-- Node Marking Method -->
        <section class="mb-20">
            <div class="flex items-center mb-8">
                <div class="bg-green-100 p-3 rounded-full mr-4">
                    <i class="fas fa-edit text-green-700 text-xl"></i>
                </div>
                <h2 class="text-3xl font-bold text-gray-900 font-serif">3. 修改节点值方法</h2>
            </div>

            <div class="grid md:grid-cols-2 gap-8">
                <!-- Algorithm Explanation -->
                <div class="bg-white rounded-xl shadow-md p-6 algorithm-card transition duration-300">
                    <h3 class="text-xl font-semibold mb-4 text-green-700">算法思路</h3>
                    <ol class="space-y-4 list-decimal pl-5">
                        <li><span class="font-medium">修改节点值</span>：遍历链表时，将每个节点的值设置为一个特殊标记</li>
                        <li><span class="font-medium">检测标记</span>：
                            <ul class="list-disc pl-5 mt-2">
                                <li>如果发现当前节点已被标记，则链表存在环</li>
                                <li>如果遍历结束无标记节点，则链表无环</li>
                            </ul>
                        </li>
                    </ol>

                    <div class="mt-6 bg-red-50 border-l-4 border-red-400 p-4">
                        <div class="flex">
                            <div class="flex-shrink-0">
                                <i class="fas fa-exclamation-circle text-red-500"></i>
                            </div>
                            <div class="ml-3">
                                <p class="text-sm text-red-700">
                                    <span class="font-medium">注意：</span> 这种方法会修改原始链表数据，可能不适用于实际生产环境，特别是在不能修改链表数据的场景下。
                                </p>
                            </div>
                        </div>
                    </div>
                </div>

                <!-- Code Example -->
                <div class="code-block">
                    <div class="code-header">
                        <span class="code-lang">Java</span>
                        <div class="ml-auto flex space-x-2">
                            <div class="w-3 h-3 rounded-full bg-red-500"></div>
                            <div class="w-3 h-3 rounded-full bg-yellow-500"></div>
                            <div class="w-3 h-3 rounded-full bg-green-500"></div>
                        </div>
                    </div>
                    <pre class="p-4 overflow-x-auto text-gray-200"><code>public class LinkedListCycleDetectorWithMarkingDemo {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    public static boolean hasCycle(ListNode head) {
        final int MARK = Integer.MIN_VALUE;
        
        while (head != null) {
            if (head.val == MARK) {
                return true; // 存在环
            }
            head.val = MARK; // 标记当前节点
            head = head.next;
        }
        return false; // 不存在环
    }

    public static void main(String[] args) {
        // 创建带环链表
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next; // 创建环

        boolean result = hasCycle(head);
        System.out.println(result ? "链表中存在环" : "链表中不存在环");
    }
}</code></pre>
                </div>
            </div>

            <div class="mt-8 bg-white rounded-xl shadow-md p-6">
                <h3 class="text-xl font-semibold mb-4 text-green-700">算法分析</h3>
                <div class="grid md:grid-cols-2 gap-4">
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <h4 class="font-medium text-gray-900 mb-2 flex items-center">
                            <i class="fas fa-check-circle text-green-500 mr-2"></i>优点
                        </h4>
                        <ul class="list-disc pl-5 text-gray-700">
                            <li>空间复杂度为 O(1)，不需要额外存储</li>
                            <li>实现简单</li>
                            <li>时间复杂度为 O(n)，线性时间</li>
                        </ul>
                    </div>
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <h4 class="font-medium text-gray-900 mb-2 flex items-center">
                            <i class="fas fa-exclamation-triangle text-yellow-500 mr-2"></i>局限性
                        </h4>
                        <ul class="list-disc pl-5 text-gray-700">
                            <li>修改了原始链表数据，可能影响其他操作</li>
                            <li>需要确定合适的标记值（不能与正常值冲突）</li>
                            <li>不适用于多线程环境</li>
                        </ul>
                    </div>
                </div>
            </div>
        </section>

        <!-- Comparison Table -->
        <section class="mb-16 bg-white rounded-xl shadow-lg overflow-hidden">
            <div class="p-6">
                <h2 class="text-2xl font-bold mb-6 text-gray-800 font-serif">算法比较</h2>
                <div class="overflow-x-auto">
                    <table class="min-w-full divide-y divide-gray-200">
                        <thead class="bg-gray-50">
                            <tr>
                                <th scope="col" class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">方法</th>
                                <th scope="col" class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">时间复杂度</th>
                                <th scope="col" class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">空间复杂度</th>
                                <th scope="col" class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">修改数据</th>
                                <th scope="col" class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">适用场景</th>
                            </tr>
                        </thead>
                        <tbody class="bg-white divide-y divide-gray-200">
                            <tr class="hover:bg-gray-50">
                                <td class="px-6 py-4 whitespace-nowrap font-medium text-purple-700">快慢指针</td>
                                <td class="px-6 py-4 whitespace-nowrap">O(n)</td>
                                <td class="px-6 py-4 whitespace-nowrap">O(1)</td>
                                <td class="px-6 py-4 whitespace-nowrap">否</td>
                                <td class="px-6 py-4 whitespace-nowrap">大多数场景，空间受限环境</td>
                            </tr>
                            <tr class="hover:bg-gray-50">
                                <td class="px-6 py-4 whitespace-nowrap font-medium text-blue-700">哈希表</td>
                                <td class="px-6 py-4 whitespace-nowrap">O(n)</td>
                                <td class="px-6 py-4 whitespace-nowrap">O(n)</td>
                                <td class="px-6 py-4 whitespace-nowrap">否</td>
                                <td class="px-6 py-4 whitespace-nowrap">需要查找环起点，空间允许</td>
                            </tr>
                            <tr class="hover:bg-gray-50">
                                <td class="px-6 py-4 whitespace-nowrap font-medium text-green-700">修改节点值</td>
                                <td class="px-6 py-4 whitespace-nowrap">O(n)</td>
                                <td class="px-6 py-4 whitespace-nowrap">O(1)</td>
                                <td class="px-6 py-4 whitespace-nowrap">是</td>
                                <td class="px-6 py-4 whitespace-nowrap">临时使用，数据可修改场景</td>
                            </tr>
                        </tbody>
                    </table>
                </div>
            </div>
        </section>

        <!-- Conclusion -->
        <section class="bg-white rounded-xl shadow-lg overflow-hidden mb-16">
            <div class="p-6">
                <h2 class="text-2xl font-bold mb-6 text-gray-800 font-serif">总结与建议</h2>
                <div class="prose max-w-none text-gray-700">
                    <p><span class="font-medium text-purple-700">快慢指针算法</span>是检测链表环的首选方法，它不需要额外空间，实现简单高效，适用于大多数场景。</p>
                    <p>当需要找出环的起始节点时，可以结合<span class="font-medium text-blue-700">哈希表方法</span>，虽然会消耗更多内存，但能提供更多信息。</p>
                    <p><span class="font-medium text-green-700">修改节点值方法</span>虽然空间效率高，但由于会改变原始数据，建议仅在特定场景下使用。</p>
                    <p class="mt-4 bg-gray-50 p-4 rounded-lg border-l-4 border-purple-500">
                        <span class="font-medium">最佳实践：</span> 在实际开发中，优先考虑快慢指针法；如果需要定位环的起点，可以先使用快慢指针确认环存在，再使用改进的快慢指针算法找出环起点，这样既保持空间效率，又能获取更多信息。
                    </p>
                </div>
            </div>
        </section>
    </main>

    <!-- Footer -->
    <footer class="bg-gray-900 text-gray-300 py-8">
        <div class="max-w-4xl mx-auto px-4 sm:px-6 lg:px-8">
            <div class="flex flex-col md:flex-row justify-between items-center">
                <div class="mb-4 md:mb-0">
                    <h3 class="text-xl font-medium text-white">技术小馆</h3>
                    <p class="mt-1">探索编程世界的奥秘</p>
                </div>
                <div>
                    <a href="http://www.yuque.com/jtostring" class="text-purple-400 hover:text-white transition duration-300">
                        <i class="fas fa-external-link-alt mr-2"></i>www.yuque.com/jtostring
                    </a>
                </div>
            </div>
            <div class="mt-8 pt-8 border-t border-gray-800 text-center text-sm">
                <p>&copy; 2023 技术小馆. 保留所有权利.</p>
            </div>
        </div>
    </footer>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>